package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by 朱城委 on 2021/7/16.<br><br>
 *
 * 四数之和
 */
public class Topic18 {

    public static void main(String[] args) {
        Topic18 instance = new Topic18();

        int[] array = new int[] {1,0,-1,0,-2,2};
        System.out.println(instance.fourSum(array, 0));

        array = new int[] {};
        System.out.println(instance.fourSum(array, 0));

        array = new int[] {2,2,2,2,2};
        System.out.println(instance.fourSum(array, 8));

        array = new int[] {-493,-482,-482,-456,-427,-405,-392,-385,-351,-269,-259,-251,-235,-235,-202,-201,-194,-189,-187,-186,-180,-177,-175,-156,-150,-147,-140,-122,-112,-112,-105,-98,-49,-38,-35,-34,-18,20,52,53,57,76,124,126,128,132,142,147,157,180,207,227,274,296,311,334,336,337,339,349,354,363,372,378,383,413,431,471,474,481,492};
        System.out.println(instance.fourSum(array, 6189));

        array = new int[] {-499,-486,-479,-462,-456,-430,-415,-413,-399,-381,-353,-349,-342,-337,-336,-331,-330,-322,-315,-280,-271,-265,-249,-231,-226,-219,-216,-208,-206,-204,-188,-159,-144,-139,-123,-115,-99,-89,-80,-74,-61,-22,-22,-8,-5,4,43,65,82,86,95,101,103,123,149,152,162,165,168,183,204,209,209,220,235,243,243,244,248,253,260,273,281,284,288,290,346,378,382,384,407,411,423,432,433,445,470,476,497};
        System.out.println(instance.fourSum(array, 3032));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            // remove duplicate
            if(i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }

            threeSum(nums, i, target - nums[i], result);
        }
        return result;
    }

    private void threeSum(int[] nums, int index, int target, List<List<Integer>> result) {
        for(int i = index + 1; i < nums.length; i++) {

            // remove duplicate
            if(i > index + 1 && nums[i - 1] == nums[i]) {
                continue;
            }

            int low = i + 1;
            int high = nums.length - 1;
            while (low < high) {
                int sum = nums[i] + nums[low] + nums[high];
                if(sum == target) {
                    result.add(Arrays.asList(nums[index], nums[i], nums[low++], nums[high--]));

                    while (low < high && nums[low] == nums[low - 1]) {
                        low++;
                    }
                }

                if(sum > target) {
                    high--;
                }

                if(sum < target) {
                    low++;
                }
            }
        }
    }
}
